package dynamicPrograming;

/**
 * 斐波那契数列的动态规划实现
 * @author le
 */
public class FibonacciDp {

    /**
     * 动态规划跑的次数
     */
    static int dpCount = 0;

    static int count = 0;

    public static void main(String[] args) {
        int n = 7;

        System.out.println("---------------------动态规划-01-------------------");
        System.out.println(getResult(n)+" 运行的次数："+dpCount);
        System.out.println("---------------------动态规划-02-------------------");
        System.out.println(fibGetResult(n)+" 运行的次数："+dpCount);
        System.out.println("---------------------递归实现-------------------");
        System.out.println(fibGetResult(n)+" 运行的次数："+count);

    }

    /**
     * 动态规划-1
     * 动态规划实现斐波那契数列
     * @param n
     * @return
     */
    static public int getResult(int n){
        int[] res = new int[n+1];
        res[0] = 1;
        dpCount++;
        res[1] = 1;
        dpCount++;
        for (int i = 2;i <= n;i++){
            res[i] = res[i-1]+res[i-2];
            dpCount++;
        }
        return res[n];
    }

    /**
     * 动态规划-2
     * 动态规划实现斐波那契数列
     * @param n
     * @return
     */
    public static int getFibGetResult(int n){
        int num1 = 0;
        int num2 = 1;
        int num = 1;

        for (int i = 2;i <= n;i++){
            num = num1+num2;
            num1 = num2;
            num2 = num;
            dpCount++;
        }

        return num;
    }

    /**
     * 递归实现斐波那契梳理
     * @param n
     * @return
     */
    public static int fibGetResult(int n){
        if (n == 0){
            count++;
            return 1;
        }else if (n == 1){
            count++;
            return 1;
        }else{
            return fibGetResult(n-1)+fibGetResult(n-2);
        }
    }
}
